package com.sxt;
/**基于二叉树结构实现元素排序处理的排序器*/
//泛型是整数类型
//结点类要有三个成员变量两个方法：1，存储元素，2，存储左子树地址 3存储右子树结点地址
// 1，判断元素对大小，放在左还是右子树的方法  2，每个节点的元素进行遍历的方法
public class BinaryTreeSort<E extends Integer> {
    /*定义结点，用内部类*/
    class Node<E extends Integer>{
        private E item;//存放元素
        private Node left;//存放左子树地址
        private Node right;//存放右子树地址
        //用构造方法，方便使用结点中的元素
        Node(E item){
            this.item = item;
        }

        /*添加结点*/
        public void addNode(Node node){
            //完成新结点中的元素与当前新结点中的元素的判断
            //如果新结点中的元素小于当前结点中的元素。那么新结点放在当前结点的左子树
            if(node.item.intValue()<this.item.intValue()){
                if(this.left == null){
                    this.left = node;
                }else {
                    //如果左子树有元素，逐层向下找到左子树为空
                    //用递归  this.left 在已经被判断的左结节点进行addNode方法
                    this.left.addNode(node);
                }
                //如果新结点中的元素大于当前结点中的元素。那么新结点放在当前结点的右子树
            }else {
                if(this.right == null){
                    this.right = node;
                }else {
                    this.right.addNode(node);
                }
            }
        }
        /*使用中序遍历*/
        public void inorderTraversal(){
           /* this.left不是当前节点，而是当前节点的左节点，
             这里遍历到当前节点左节点为null的时候，开始弹栈，
             弹栈出一个节点后，判断当前节点右节点是否为null,
             这里运行时到下一个节点，是由递归多次调用的效果，*/
            //找到最左则的那个节点
            //用递归  不断向下压栈直到找到最后一个左子树，然后弹栈
            if(this.left != null)this.left.inorderTraversal();
            System.out.println(this.item);
            //在递归时已经打印出来
            if (this.right != null)this.right.inorderTraversal();
        }
    }

    private Node root;//存放树的根节点的地址
    //添加元素
    public void add(E element){
        //实例化新结点对象
        Node<E> node = new Node<>(element);
        //判断是否根结点
        if(this.root == null){
            this.root = node;
        }else {
            //将根节点放入addNode方法中
            this.root.addNode(node);
        }
    }
    //对元素进行排序
    public void sort(){
        //判断根结点是否为空
        if(this.root == null)return;
        //如果不是空，要遍历排序
        this.root.inorderTraversal();
    }

    public static void main(String[] args) {
        BinaryTreeSort<Integer> sort = new BinaryTreeSort<>();
        //5,3,1,6,9,8
        sort.add(5);
        sort.add(3);
        sort.add(1);
        sort.add(6);
        sort.add(9);
        sort.add(8);
        sort.sort();
    }
}
